package com.fps.webshop.question.question0200_0299;

import com.fps.webshop.question.common.TreeNode;

/**
 * 226. 翻转二叉树
 * 
 * 翻转一棵二叉树。
 * 示例：
 * 
 * 输入：
 *      4
 *    /   \
 *   2     7
 *  / \   / \
 * 1   3 6   9
 * 
 * 输出：
 *      4
 *    /   \
 *   7     2
 *  / \   / \
 * 9   6 3   1
 */
public class Question226 {
	
	/**
	 * 第一次提交，二叉树递归调用
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		0 ms	35.8 MB	Java	2021/08/23 15:04
	 * 
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：35.8 MB, 在所有 Java 提交中击败了60.02%的用户
	 */
	public static TreeNode invertTree1(TreeNode root) {
		return getTheTree(root,root);
    }
	
	public static TreeNode getTheTree(TreeNode root,TreeNode nowNode) {
		if(nowNode==null) {
			return root;
		}else {
			TreeNode tmp = nowNode.left;
			nowNode.left = nowNode.right;
			nowNode.right = tmp;
			getTheTree(root,nowNode.left);
			getTheTree(root,nowNode.right);
			return root;
		}
    }
	//优化，也可以，速度和之前一样
	public static TreeNode getTheTree2(TreeNode root,TreeNode nowNode) {
		if(nowNode!=null) {
			TreeNode tmp = nowNode.left;
			nowNode.left = nowNode.right;
			nowNode.right = tmp;
			getTheTree2(root,nowNode.left);
			getTheTree2(root,nowNode.right);
		}
        return root;
    }
	
	/**
	 * 第2次提交，参考官方解答优化递归方案和代码
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		0 ms	35.9 MB	Java	2021/08/23 15:08
	 * 
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：35.9 MB, 在所有 Java 提交中击败了44.27%的用户
	 */
	public static TreeNode invertTree2(TreeNode root) {
		if(root==null) {
			return null;
		}
		TreeNode left = invertTree2(root.left);
		TreeNode right = invertTree2(root.right);
		root.left = right;
		root.right = left;
		return root;
    }
	
	public static void main(String[] args) {
		TreeNode root = new TreeNode(41);
		TreeNode leftNode1 = new TreeNode(-57);
		TreeNode rightNode1 = new TreeNode(-57);
		root.left = leftNode1;
		root.right = rightNode1;
		
		TreeNode rightNode2 = new TreeNode(67);
		leftNode1.right = rightNode2;
		
		TreeNode leftNode3 = new TreeNode(67);
		rightNode1.left = leftNode3;
		
		System.out.print(invertTree1(root));
		
	}
}
